Vector quantization technologies are usually deployed in stream media coding, a common one of the technologies is lattice vector quantization which is quite widely used in low-rate scenarios. In audio coding, for example, the quantization technology deployed in Transform Code Excite (TCX) part of the widely used Extend Adaptive Multi-Rate Wideband codec (AMR-WB+) audio coding algorithm is a multi-rate lattice vector quantization technique built on RE8—an eight-dimensional lattice known to ordinary skilled artisans as the Gosset lattice.
In the TCX part of the AMR-WB+ audio coding algorithm, the multi-rate lattice vector quantization approach is applied as the quantization approach. The multi-rate lattice vector quantization approach is applied on preshaped spectral data by groups each having eight values, and quantizes the eight values as elements in the RE8 set based on a principle of proximity. In the algorithm, a set of elements is selected from the RE8 with the quantization, which is defined as RE8=2D8∪{2D8+(1, . . . , 1)}, where D8={(x1, x2, . . . , x8)εZ8|x1+ . . . +x8 is even}. Therefore, the sum of all elements in the RE8 set is a multiple of 4. Thus, the quantization approach includes searching the 2D8 set for an element closest to the original data, searching the 2D8+(1, 1, 1, . . . , 1) set for an element closest to the original data, and comparing the two elements searched out to obtain a result, i.e. an initial vector, which is a group of integer data (x0, x1, . . . , xn-1) denoted by ck. Because the inputted data is divided into groups each having eight values, the resulting ck is actually (x0, x1, . . . , x7).
Subsequently, basic codebooks of Q0, Q2, Q3, Q4 are searched for the ck. If no ck is found in the basic codebooks, the basic codebooks are extended with the ck through Voronoi extension, so that a corresponding basic codebook index and an extended codebook index are determined. The basic codebooks of Q0, Q2, Q3, Q4 are shown in Table 1 below
TABLE 1Basic codebooksSphereKaLeaderCombinationSignSizeQ0Q2Q3Q40{0, 0, 0, 0, 0, 0, 0, 0}1X20{1, 1, 1, 1, 1, 1, 1, 1}1128128XX81{2, 2, 0, 0, 0, 0, 0, 0}284112XX162{2, 2, 2, 2, 0, 0, 0, 0}70161120X223{3, 1, 1, 1, 1, 1, 1, 1}81281024X644{4, 0, 0, 0, 0, 0, 0, 0}8216XX245{2, 2, 2, 2, 2, 2, 0, 0}28641792X426{3, 3, 1, 1, 1, 1, 1, 1}281283584X727{4, 2, 2, 0, 0, 0, 0, 0}16881344X328{2, 2, 2, 2, 2, 2, 2, 2}1256256X629{3, 3, 3, 1, 1, 1, 1, 1}561287168X8010{4, 2, 2, 2, 2, 0, 0, 0}280328960X12811{4, 4, 0, 0, 0, 0, 0, 0}284112X15812{5, 1, 1, 1, 1, 1, 1, 1}81281024X8213{3, 3, 3, 3, 1, 1, 1, 1}701288960X8814{4, 2, 2, 2, 2, 2, 2, 0}561287168X13615{4, 4, 2, 2, 0, 0, 0, 0}420166720X17816{5, 3, 1, 1, 1, 1, 1, 1}561287168X32817{6, 2, 0, 0, 0, 0, 0, 0}564224X19218{4, 4, 4, 0, 0, 0, 0, 0}568448X33629{6, 2, 2, 2, 0, 0, 0, 0}280164480X39220{6, 4, 2, 0, 0, 0, 0, 0}33682688X120221{7, 7, 1, 1, 1, 1, 1, 1}81281024X102422{8, 0, 0, 0, 0, 0, 0, 0}8216X64823{6, 6, 0, 0, 0, 0, 0, 0}284112X103224{8, 2, 2, 0, 0, 0, 0, 0}16881344X108825{8, 4, 0, 0, 0, 0, 0, 0}564224X164226{9, 1, 1, 1, 1, 1, 1, 1}81281024X250427{10, 2, 0, 0, 0, 0, 0, 0}564224X204828{8, 8, 0, 0, 0, 0, 0, 0}284112X282439{10, 6, 0, 0, 0, 0, 0, 0}564224X518430{12, 0, 0, 0, 0, 0, 0, 0}8216X524831{12, 4, 0, 0, 0, 0, 0, 0}564224X500032{10, 10, 0, 0, 0, 0, 0, 0}284112X960833{14, 2, 0, 0, 0, 0, 0, 0}564224X620834{12, 8, 0, 0, 0, 0, 0, 0}564224X1638435{16, 0, 0, 0, 0, 0, 0, 0}8216X
Codewords are generated from appropriate permutations of the components of a few basic vectors called “Leaders” or “characteristic codebooks,” and are distributed on the surface of respective spheres. “Sphere” indicates the size of a sphere, “Size” indicates a number of the codewords derived from permutation and combination of the leader, and “Ka” identifies the respective leaders, with each leader being identified by a different Ka value. The value of Sphere (S) is a quarter of the sum of all components of the leader each to the power of four, i.e.
  S  =            1      4        ⁢                  (                              x            1            4                    +                      x            2            4                    +          …          +                      x            7            4                    +                      x            8            4                          )            .      Each leader corresponds to an S having a different value. In the coding, each value of S corresponds to a value of Ka. In the case of an 8-dimensional vector, a corresponding Ka can be searched out with only the calculated value of S of the 8-dimensional vector, and thus a leader to which the value of S belongs may be determined from the value of Ka. The basic codebooks of the leaders are further shown in Table 1. The basic codebooks are divided into Q0, Q2, Q3 and Q4. The Q0 contains only one leader, and the Q2, Q3, and Q4 contain 3, 8 and 28 leaders respectively, where Q2⊂Q3, and Q3⊂Q4, as shown in Table 1.
After the basic codebook to which the ck belongs is determined, assuming that the ck is a sample from a set of elements (a0, a1, . . . , aq-1) and w(i) is the number of element ai in the sample, thus the number of possible states of Leader L is k(l) given as follows:
      K    ⁡          (      l      )        =                    C        n                  w          0                    +                        ∏                      i            =            1                                q            -            1                          ⁢                                  ⁢                  C                      n            -                                          ∑                                  j                  =                  0                                                  i                  -                  1                                            ⁢                                                          ⁢                              w                i                                                          w            i                                =                  n        !                              ∏                      i            =            0                                q            -            1                          ⁢                                  ⁢                              w            i                    !                    
If d(k)=i, xk=ai, and wik is the number of element ai in (x0, x1, . . . , xn-1), an index of the (x0, x1, . . . , xn-1) is coded as follows:
  t  =            ∑              k        =        1            n        ⁢                  ⁢                            (                      n            -            1            -            k                    )                                      ∏                          i              =              0                                      q              =              1                                ⁢                                          ⁢                                    (                              w                i                k                            )                        !                              ⁢              (                              ∑                          j              =              0                                                      d                ⁡                                  (                  k                  )                                            -              1                                ⁢                                          ⁢                      w            i            k                          )            
In decoding, vector d(k) is obtained in sequence using the formula below, where k=0, . . . 7:
            I      ⁡              (                                            d              ⁡                              (                k                )                                      -            1                    ,          k                )              ≤          t      -                        ∑                      j            =            0                                k            -            1                          ⁢                                  ⁢                  I          ⁡                      (                                                            d                  ⁡                                      (                    j                    )                                                  -                1                            ,              j                        )                                <          I      ⁡              (                              d            ⁡                          (              k              )                                ,          k                )                        I      ⁡              (                  p          ,          k                )              =                                        (                          n              -              1              -              k                        )                    !                                      ∏                          I              =              0                                      q              -              1                                ⁢                                          ⁢                                    (                              w                i                k                            )                        !                              ⁢                        ∑                      j            =            0                    p                ⁢                                  ⁢                  w          j          k                    
Then (x0, x1, . . . , xn-1) is derived from d(k) based on that d(k)=i and xk=ai. The above solution is disadvantageous at least in that multiple irregular factorials are calculated during coding and decoding, furthermore, the calculation of these random factorials can hardly be simplified by lookup process, resulting in high calculation complexity.